package cover.alg;


import java.util.LinkedList;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultEdge;

import cover.vertex.Vertex;

/**
 * Hybrid Genetic Algorithm
 *
 */

public class HGA {
	
	private Set<Vertex> cover;
	private Integer usefull;
	Graph<Vertex, DefaultEdge> graph;
	Integer populations;
	
	public HGA(Graph<Vertex, DefaultEdge> graph,int t) {
		usefull = 0;
		this.graph = graph;
		populations = t;
		cover = null;
	}
	/**
	 * initialize P(t) randomly
	 * select best 50% chromosomes from P(t) and put them in P(t+1)
	 * LOT on (HVX on P(t)) to P(t+1)
	 * @param graph
	 * @param t
	 * @return
	 */
	private Set<Vertex> hga (Graph<Vertex, DefaultEdge> graph,int t){
		LinkedList<Set<Vertex>> firstPopulation = Utils.getFirstPopulation(graph);
		usefull++;
		LinkedList<Set<Vertex>> nextPopulation = new LinkedList<Set<Vertex>>();
		for(int i = 0;i < t;i++){
			for(int j=0;j<firstPopulation.size()/2;j++){
				nextPopulation.add(firstPopulation.get(j));
			}
			
			for(int j=0;j<firstPopulation.size()-1;j+=2){
				HVX child = new HVX(firstPopulation.get(j),firstPopulation.get(j+1),graph);
				Set<Vertex> newCover = child.makeChild();
				if(nextPopulation.contains(newCover))
					newCover = Utils.mutationOneAnotherGreedy(newCover,Utils.copyOfGraph(graph));
				
				if(nextPopulation.size() == 0)
					nextPopulation.add(newCover);
				for(int k=0,check = 0;k<nextPopulation.size() && check==0;k++){
					if(nextPopulation.get(k).size()>=newCover.size()){
						nextPopulation.add(k,newCover);
						check = 1;
					}
					else if(k==nextPopulation.size()-1){
						nextPopulation.add(newCover);
						check = 1;
					}
				}
			}
			if(nextPopulation.getFirst().size()<firstPopulation.getFirst().size())
				usefull++;
			firstPopulation = nextPopulation;
			nextPopulation = new LinkedList<Set<Vertex>>();
		}
		return firstPopulation.getFirst();
	}
	public Set<Vertex> getCover() {
		if (cover==null){
			cover = hga(graph,populations);
			for(Vertex vertex : graph.vertexSet()){
				if(cover.contains(vertex))
					vertex.addToCover();
			}
			return cover;
	}
	return cover;
	}
	
	public int getUsefull() {
		return usefull;
	}
}
